7.3 eventual consistency 還沒寫ＱＱ

這章會來聊聊 consistency
ACID 中的 consistency 跟 CAP 理論中的 consistency 是不同的，
可以看看這篇鐵人賽文章：Day 2 - 我的C是你的C嗎，介紹CAP Theorem與ACID/BASE

這裏我們在講 replica 之間的 consistency，
該怎麼定義兩個 replica 是一致的？
什麼時候一致？

7-1 Two phase commit

這堂課的上半學期有講到 ACID 的 atomicity，
如果 transaction 會發生在多個節點上，
我們仍希望維持 atomicity：
要馬全部的節點 commit 這個 transaction，
要馬全部的節點放棄這個 transaction 並 rollback。

因此，需要全部的節點有某種 agreement：決定要 abort 或 commit。
而且只要有一個節點掛掉，全部都會 abort。

Consensus vs Atomic commit

講到節點要達成某種協議，跟第六章的 consensus 好像，
所以這邊比較一下。
![[Screen Shot 2021-09-24 at 11.02.21 PM.png]]

Two phase commit

Two phase commit 是一個確保多個節點上的 atomic commitment 的協定

一開始 client 發送 transaction 給每個 replica，這些 replica 就執行這個 transaction。

而當 client 要 commit 時：

1. 傳送 commit request 給 commit coordinator
2. coordinator 傳送 "prepare"訊息 給其他 replicas，問問他們可不可以 commit？如果 replica 們都確認自己的狀態是可以 commit 的，才會傳 yes
   replicas 們只要跟 coordinator 保證他們是可以 commit 的狀態，
   就不能出爾反爾，
   因此這時候不能任意的 commit 或 abort 任何東西，
   以免之後跟 coordinator 的決定不一致。
3. 若有任何一個節點說不，全部節點就會 abort、rollback。反之，全部說好，則 coordinator 會再告訴大家可以 commit 了。

Coordinator 掛掉怎麼辦？

經過前幾章的洗禮，大家都很怕某個節點掛了會影響整個系統的運行（SPOF）。
以上面的演算法來說，coordinator 佔有很重要的地位，如果掛掉了會有什麼樣的影響？
一般來說，coordinator 作出決定後會馬上寫入硬碟，才開始廣播，
這樣的話如果不幸掛了，開機恢復後還可以讀回剛剛做的決定，再廣播出去。

然而送出 prepare 訊息，並已經做決定，還沒廣播給節點們就掛了的話，
其他節點會動彈不得。（畢竟他們已經給 coordinator 承諾了，不能隨意改變狀態以免違約）

Fault-tolerant two-phase commit

這裡將介紹一個能夠容錯的 two-phase commit，基於 Paxos Commit。
使用 total order broadcast！（或是 consensus，畢竟兩者可以互換）
這個想法就是，
commit 時每個節點都會廣播自己的投票給其他節點，
而其他節點就會開始算，只要收到所有其他節點的 yes，他就可以 commit 這個 transaction；如果收到一個 no，就可以馬上 abort。

而既然是 total order，每個節點 deliver 訊息的順序是相同的，
因此不需要擔心 race condition，只要已經收到某個節點投票，接下來又收到同個節點的投票都直接丟掉不算。

如果是其中一個 replica 掛了，
該怎麼處理呢？
如果 A 懷疑 B 掛掉了（timeout），A 會幫 B 投 no。
就算 B 其實只是反應慢，而後投 yes，
但就像前面說的，感謝 total order broadcast，又每個 replica 只會接受第一票，所以不會造成 replica 之間不一致的狀況。

7-2 Linearizability

linearizability 確保永遠只讀到最新的數值，
又稱為 strong consistency。

這聽起來跟第 5 章提到的 read-after write 很相似。
read-after write consistency 只保證同個節點寫完後能讀到至少是自己寫的之後的資料，
而 linearizability 則更嚴格，要能確保不同的節點都能讀取到最新的資料。

![[Screen Shot 2021-09-24 at 11.16.19 PM.png]]
這裡只專注於從 client 的角度出發。
當 client 1 set(x, v1)，client2 也希望能讀到 v1。
這不是 happens-before 關係，happens-before 是基於發送和收訊息而訂出的順序關係，而這裡就算 client 1 與 client 2 沒有任何訊息往來，單就時間來說，仍希望能讀到最新的數值。

所以要看系統是否 linearizable，我們需要考慮 client 間 operation 的時間重疊下，是否還能得到最新的結果。

使用 quorum reads/writes 難道不能保證每個節點都能讀到最新數值嗎？

![[Screen Shot 2021-09-24 at 11.17.38 PM.png]]
以此圖來看，第一個 client1 發出 set，而 client2 get 的當下只有 只有 A 成功被更新，他也剛好得到 A、B 回應，並由 timestamp 知道 v1 是最新的數值。
但 client3 get 時，回應的剛好只有兩個還沒更新到數值的節點，所以這不符合 linearizability。

linearizable ABD 演算法

當 client 發現 get 到不同的數值，會幫忙再發送 set 新數值給過時的節點或沒有回應的節點，這也是前面提過的 read repair。
這個 get 的過程只有等到 quorum 個節點都有成功 read repair 或是一開始就是最新數值，才會結束。

這方法又叫 ABD 演算法，確保 linearizable reads and writes，每次的 get 或 set 都讓至少 quorum 個節點擁有最新的數值。

7-3 Eventual consistency